package HighMethod07;

/**
 * ClassName:    demo
 * Package:    HighMethod07
 * Description:     动态规划
 * Datetime:    2021/4/24 0024   21:17
 * Author: 沈新源
 */

/**
 * 分治算法与
 */
public class demo {

    //方法一：递归，有重复求解的部分
    public static int LCSLength(char[] X, char[] Y, int i, int j) {

        if (i == 0 || j == 0) return 0;

        else if (i > 0 && j > 0 && X[i] == Y[j])
            return LCSLength(X, Y, i - 1, j - 1) + 1;
        else
            return Math.max(LCSLength(X, Y, i - 1, j), LCSLength(X, Y, i, j - 1));

    }

    //方法二：递归，查表（）
    public static int LCSLength(char[] X, char[] Y, int i, int j, int[][] c, int[][] s) {

        if (i == 0 || j == 0) return 0;

        else if (c[i][j] > 0)
            return c[i][j];
        else if (X[i] == Y[j]) {
            c[i][j] = LCSLength(X, Y, i - 1, j - 1,c,s) + 1;
            s[i][j] = 1;                //1顺主对角线
        } else {
            int lena = LCSLength(X, Y, i - 1, j,c,s);
            int lenb = LCSLength(X, Y, i, j - 1,c,s);
            if (lena > lenb) {
                c[i][j] = lena;
                s[i][j] = 2;            //2行减一
            } else {
                c[i][j] = lenb;
                s[i][j] = 3;            //3列减一
            }
        }
        return c[i][j];
    }

    //方法三：非递归
    public static int LCSLength(char[] X, char[] Y, int[][] c, int[][] s) {
        for(int i=1;i<X.length;i++){        //注意循环的起始下标
            for(int j =1;j<Y.length;j++){
                if(X[i] == Y[j]){
                    c[i][j] = c[i-1][j-1]+1;
                    s[i][j] =1;
                }else {
                    if(c[i-1][j] > c[i][j-1]){
                        c[i][j] = c[i-1][j];
                        s[i][j] = 2;
                    }
                    else {
                        c[i][j] = c[i][j-1];
                        s[i][j] = 3;
                    }
                }
            }
        }
        return c[X.length-1][Y.length-1];
    }



    //输出二维数组
    public static void PrintCharArray(int[][] arr){
        for(int i=0;i<arr.length;i++){
            for(int j =0;j<arr[i].length;j++){
                System.out.printf("%4d",arr[i][j]);
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        char[] X = {'#', 'A', 'B', 'C', 'B', 'D', 'A', 'B'};
        char[] Y = {'#', 'B', 'D', 'C', 'A', 'B', 'A'};

//        方法一
//        int maxLen = LCSLength(X,Y,X.length-1,Y.length-1);

//        方法二
        int[][] c = new int[X.length][Y.length];
        int[][] s = new int[X.length][Y.length];
//        int maxLen = LCSLength(X, Y, X.length - 1, Y.length - 1, c,s);


//        方法三
        int maxLen = LCSLength(X, Y, c,s);
        PrintCharArray(c);
        PrintCharArray(s);
        System.out.println("最长公共子序列的长度：" + maxLen);

        //打印出最长公共子序列
        BackPack(X,X.length-1,Y,Y.length-1,s);

        //还有一个动态规划的例子，LeetCode的打家劫舍I、II、III
    }

    //递归输出最长公共子序列
    private static void BackPack(char[] X, int i, char[] Y, int j,int[][] s) {
        if(i==0||j==0) return;
        if(s[i][j] == 1){
            BackPack(X,i-1,Y,j-1,s);
            System.out.printf("%c",X[i]);
        }else if(s[i][j] == 2){
            BackPack(X,i-1,Y,j,s);
        }else {
            BackPack(X,i,Y,j-1,s);
        }
    }
}
